// 链表

/**
 * 双向链接节点
 */
class DoubleLinkedNode {
    constructor(val, next, prev) {
        this.val = val;
        this.next = next;
        this.prev = prev;
    }
}

/**
 * 双向链表
 */
class DoubleLinkedList {
    constructor() {
        // 当前数组大小
        let _size = 0;
        Object.defineProperty(this, 'size', {
            get() {
                return _size;
            },
            set() {
                throw new Error('无法修改size属性')
            },
            configurable: false,
        })

        let _headNode = null;
        let _tailNode = null;
        /**
         * 添加元素
         * @param ele
         */
        this.add = function (ele) {
            let curr = new DoubleLinkedNode(ele, null, null);
            if (_headNode == null) {
                _headNode = curr;
            } else {
                _tailNode.next = curr;
                curr.prev = _tailNode;
            }
            _tailNode = curr;
            _size++;
        }

        let thisObj = this;
        let findNodeByIndex = function (i) {
            if (thisObj.outRange(i)) {
                throw Error("超出数组范围")
            }

            let find = _headNode;
            for (let findIndex = 0; findIndex < i; findIndex++) {
                find = find.next;
            }

            return find;
        }

        /**
         * 在指定索引添加元素
         * @param i 指定索引
         * @param ele 被添加元素
         */
        this.addByIndex = function (i, ele) {
            let curr = new DoubleLinkedNode(ele, null, null);
            let find = findNodeByIndex(i);
            let prevNode = find.prev;
            if (prevNode == null) {
                curr.next = find;
                find.prev = curr;
                _headNode = curr;
            } else {
                curr.next = prevNode.next;
                if (curr.next != null) {
                    curr.next.prev = curr;
                }
                prevNode.next = curr;
                curr.prev = prevNode;
            }
            if (curr.next == null) {
                _tailNode = curr;
            }

            _size++;
        }


        /**
         * 根据索引值找元素
         * @param ele
         */
        this.findByIndex = function (i) {
            return findNodeByIndex(i).val;
        }

        /**
         * 寻找指定元素的索引
         * @param ele
         * @returns {number}
         */
        this.findIndexByEle = function (ele) {
            let find = _headNode;
            let index = -1;
            while (find != null) {
                index++;
                if (find.val == ele) {
                    return index;
                }
                find = find.next;
            }
            return -1;
        }

        let finEle = function (ele) {
            let find = _headNode;
            while (find != null) {
                if (find.val == ele) {
                    return find;
                }
                find = find.next;
            }
            return null;
        }

        /**
         * 是否存在指定元素
         * @param ele
         * @returns
         */
        this.contain = function (ele) {
            let find = finEle(ele);
            if (find != null) {
                return true;
            }
            return false;
        }
        /**
         * 删除指定元素
         * @param ele
         */
        this.remove = function (ele) {
            let eleNode = finEle(ele);
            if (eleNode != null) {
                // 修改上一个元素的next
                let prevNode = eleNode.prev;
                if (prevNode == null) {
                    _headNode = eleNode.next;
                } else {
                    prevNode.next = eleNode.next;
                    prevNode.prev = prevNode;
                }
                if (eleNode.next == null) {
                    _tailNode = eleNode.prev;
                }

                eleNode.prev = null;
                eleNode.next = null;

                _size--;
            }
        }

        /**
         * 移除索引i上的元素
         * @param i 索引i
         */
        this.removeByIndex = function (i) {
            let delEle = findNodeByIndex(i);
            let prevNode = delEle.prev;
            if (prevNode == null) {
                if (delEle.next != null) {
                    _headNode = delEle.next;
                    delEle.prev = null;
                } else {
                    _headNode = null;
                    _tailNode = null;
                }
            } else {
                prevNode.next = delEle.next;
                if (prevNode.next == null) {
                    _tailNode = prevNode;
                } else {
                    delEle.next.prev = prevNode;
                }
                delEle.prev = null;
                delEle.next = null;
            }
            _size--;
        }


        /**
         * 把链表转换为数组
         * @returns {*}
         */
        this.toArray = function () {
            if (_headNode == null) {
                return [];
            }
            let newArr = new Array(this.size);
            let curr = _headNode;
            let i = 0;
            while (curr != null) {
                newArr[i] = curr.val;
                i++;
                curr = curr.next;
            }
            return newArr;
        }
    }


    /**
     * 判断i是否在范围内
     * @param i 索引
     * @returns {boolean}
     */
    isRange(i) {
        if (i < 0 || i >= this.size) {
            return false;
        }
        return true;
    }

    /**
     * 判断i是否超出范围
     * @param i
     * @returns {boolean}
     */
    outRange(i) {
        if (this.isRange(i)) {
            return false;
        }
        return true;
    }

}

/**
 * 链接节点
 */
class LinkedNode {
    constructor(val, next) {
        this.val = val;
        this.next = next;
    }
}

/**
 * 链表
 */
class LinkedList {
    constructor() {
        // 当前数组大小
        let _size = 0;
        Object.defineProperty(this, 'size', {
            get() {
                return _size;
            },
            set() {
                throw new Error('无法修改size属性')
            },
            configurable: false,
        })

        let _headNode = null;
        let _tailNode = null;
        /**
         * 添加元素
         * @param ele
         */
        this.add = function (ele) {
            let curr = new LinkedNode(ele, null);
            if (_headNode == null) {
                _headNode = curr;
            } else {
                _tailNode.next = curr;
            }
            _tailNode = curr;
            _size++;
        }

        let thisObj = this;
        let findNodeByIndex = function (i) {
            if (thisObj.outRange(i)) {
                throw Error("超出数组范围")
            }

            let find = _headNode;
            for (let findIndex = 0; findIndex < i; findIndex++) {
                find = find.next;
            }

            return find;
        }

        /**
         * 在指定索引添加元素
         * @param i 指定索引
         * @param ele 被添加元素
         */
        this.addByIndex = function (i, ele) {
            if (this.outRange(i)) {
                throw Error("超出数组范围")
            }
            let curr = new LinkedNode(ele, null);
            if (i == 0) {
                curr.next = _headNode;
                _headNode = curr;
            } else {
                let find = findNodeByIndex(i - 1);
                curr.next = find.next;
                find.next = curr;
                if (_tailNode == find) {
                    _tailNode = curr;
                }
            }
            _size++;
        }

        /**
         * 根据索引值找元素
         * @param ele
         */
        this.findByIndex = function (i) {
            return findNodeByIndex(i).val;
        }

        /**
         * 寻找指定元素的索引
         * @param ele
         * @returns {number}
         */
        this.findIndexByEle = function (ele) {
            let find = _headNode;
            let index = -1;
            while (find != null) {
                index++;
                if (find.val == ele) {
                    return index;
                }
                find = find.next;
            }
            return -1;
        }

        let finEle = function (ele) {
            let find = _headNode;
            while (find != null) {
                if (find.val == ele) {
                    return find;
                }
                find = find.next;
            }
            return null;
        }

        /**
         * 是否存在指定元素
         * @param ele
         * @returns
         */
        this.contain = function (ele) {
            let find = finEle(ele);
            if (find != null) {
                return true;
            }
            return false;
        }
        let finPrevOfEle = function (ele) {
            let find = _headNode;
            let prev = null;
            while (find != null) {
                if (find.val == ele) {
                    return prev;
                }
                prev = find;
                find = find.next;
            }
            return null;
        }

        /**
         * 移除指定元素
         * @param ele 移除指定元素
         */
        this.remove = function (ele) {
            if (_headNode != null && _headNode.val == ele) {
                if (_tailNode == _headNode) {
                    // 当删除的元素为第一个元素
                    _tailNode = null;
                }
                let tmp = _headNode;
                _headNode = _headNode.next;
                tmp.next = null
                _size--;
                return;
            }

            let prevNode = finPrevOfEle(ele);
            if (prevNode != null) {
                let delObj = prevNode.next;
                prevNode.next = delObj.next;
                if (delObj == _tailNode) {
                    // 当删除的元素为最末位元素
                    _tailNode = prevNode;
                }
                delObj.next = null;
                _size--;
            }
        }

        /**
         * 删除索引i上的元素
         * @param i 索引i
         */
        this.removeByIndex = function (i) {
            if (_size <= 0) {
                throw Error("超出数组范围")
            }
            if (i == 0) {
                if (_headNode == _tailNode) {
                    _tailNode = null;
                }
                let tmp = _headNode;
                _headNode = _headNode.next;
                tmp.next = null
            } else {
                let prev = findNodeByIndex(i - 1);
                let cur = prev.next;
                if (cur == _tailNode) {
                    _tailNode = prev;
                }
                prev.next = cur.next;
                cur.next = null;
            }
            _size--;
        }

        /**
         * 把链表转换为数组
         * @returns {*}
         */
        this.toArray = function () {
            if (_headNode == null) {
                return [];
            }
            let newArr = new Array(this.size);
            let curr = _headNode;
            let i = 0;
            while (curr != null) {
                newArr[i] = curr.val;
                i++;
                curr = curr.next;
            }
            return newArr;
        }
    }


    /**
     * 判断i是否在范围内
     * @param i 索引
     * @returns {boolean}
     */
    isRange(i) {
        if (i < 0 || i >= this.size) {
            return false;
        }
        return true;
    }

    /**
     * 判断i是否超出范围
     * @param i
     * @returns {boolean}
     */
    outRange(i) {
        if (this.isRange(i)) {
            return false;
        }
        return true;
    }
}

